package com.eric.data;

import java.io.File;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

import com.eric.utils.Reader;

/**
 * 数据格式：attr1,attr2,attr3...attrN <br>
 * 一行一个
 * 
 * @author eric
 *
 */
public class Apriori {

	static private boolean endTag = false;
	static private List<List<String>> cItemset;
	static private List<List<String>> ckItemset;
	static private Map<List<String>, Integer> lItemset;
	static private Map<List<String>, Integer> lkItemset;

	protected static Map<List<String>, Integer> result = new HashMap<>();

	static List<List<String>> record = new ArrayList<List<String>>();

	static double MIN_SUPPORT;

	double MIN_SUPPORT_PERCENTAGE = 0.008;

	static Map<List<String>, Double> confItemset = new HashMap<List<String>, Double>();

	public Apriori(String input) {
		record = Reader.read2ListArrays(input);
		MIN_SUPPORT = Math.round(record.size() * MIN_SUPPORT_PERCENTAGE);

		// TextFactory tf = new SimpleTextFactory();
		// AbstractTextWorker tw =
		// tf.createTextWorker(WorkerType.Ansj_SEG.getName());
		//
		// for (int i = 0; i < attrList.size(); i++) {
		// tw.produce(attrList.get(i).toString());
		// record.add(tw.result());
		// }
	}

	public static void main(String[] args) throws Exception {
		Apriori ap = new Apriori("/home/eric/tmp/123.txt");
		ap.process();
		PrintWriter pw = new PrintWriter(new FileWriter(new File("/home/eric/tmp/jmall_cart_apriori_result.txt")));
		for (Entry<List<String>, Integer> entry : result.entrySet()) {
			pw.println(entry.toString());
		}
		pw.flush();
		pw.close();
		// ListUtils.printList(result);
	}

	public void process() {
		cItemset = getFirstCandidate();

		lItemset = getSupportedItemset(cItemset);

		// getLKitemset(lItemset);

		while (endTag != true) {

			ckItemset = getNextCandidate(lItemset);
			lkItemset = getSupportedItemset(ckItemset);

			if (lkItemset.size() != 0)
				getLKitemset(lkItemset);

			cItemset = ckItemset;
			lItemset = lkItemset;
		}
	}

	/**
	 * 将2维record转换成原始的候选2维cItemset（list of list)<br>
	 * ， 每一个iItemset包含的list，只包含1个元素
	 * 
	 * @return
	 */
	public static List<List<String>> getFirstCandidate() {

		List<List<String>> cItemset = new ArrayList<List<String>>();
		List<String> tempLine = new ArrayList<String>();

		// 将2维的record降成1维的list，并去重
		for (int i = 0; i < record.size(); i++) {// 外层循环，遍历record
			for (int j = 0; j < record.get(i).size(); j++) {// 内层循环，遍历第i行record
				if (tempLine.contains(record.get(i).get(j)))// 去重
					;
				else {
					tempLine.add(record.get(i).get(j));// 将第i行record的第j个元素添加到临时的list
				}
			}
		}

		// 将1维的临时list，转换成2维的list of lists，这时，list所包含的每一个list只包含1个元素
		for (int i = 0; i < tempLine.size(); i++) {// 遍历临时list
			List<String> str = new ArrayList<String>();
			str.add(tempLine.get(i));
			cItemset.add(str);
		}
		return cItemset;
	}

	/**
	 * 从cItemset（候选集）中提取大于MIN_SUPPORT的支持集<br>
	 * 算法是，取第i行的cItemset，再在cItemset中进行循环查找，如果第i行的cItemset全部包含在第k行的cItemset，则第i行的计数器+1<br>
	 * 再判断第i行的计数器是否大于MIN_SUPPORT，如果是，则放入supportedItemset
	 * 
	 * @param cItemset
	 * @return
	 */
	static Map<List<String>, Integer> getSupportedItemset(List<List<String>> cItemset) {
		Map<List<String>, Integer> supportedItemset = new HashMap<List<String>, Integer>();

		boolean end = true;

		for (int i = 0; i < cItemset.size(); i++) {
			int count = countItemFrequence(cItemset.get(i));

			if (count >= MIN_SUPPORT) {
				supportedItemset.put(cItemset.get(i), count);// 第i行的list，以及其计数
				end = false;// 如果任意1个cItemset(i)的计数大于支持度，继续循环
			}
		}
		endTag = end;
		// System.out.println(\"value of the endTag here !!!\"+endTag);
		return supportedItemset;
	}

	/**
	 * COUNT一个list在"List"<"List"<"String">" record中出现的次数<br>
	 * 原则是：第i行record，必须全部包含第k个list元素
	 * 
	 * @param list
	 * @return
	 */
	static int countItemFrequence(List<String> list) {
		int count = 0;

		for (int i = 1; i < record.size(); i++) {// 外层，遍历record
			boolean notInCurRecord = false;

			for (int k = 0; k < list.size(); k++) {// 内层，遍历待计数的list
				if (!record.get(i).contains(list.get(k))) {// 第i行record列表
															// 不包含当第k个list元素
					notInCurRecord = true;
					break;// 跳出内层循环，即跳过本行record，去下一行record进行list查找
				}
			}

			if (notInCurRecord == false) {// 如果list所有元素都能在第i行record找到，则计数器+1
				count++;
			}
		}

		return count;
	}

	/**
	 * method following is the getNextCandidata usually can be known as get Ck
	 * from Lk-1
	 */
	private static List<List<String>> getNextCandidate(Map<List<String>, Integer> lItemset) {
		List<List<String>> nextItemset = new ArrayList<List<String>>();
		List<List<String>> preItemset = getLItemset(lItemset);

		// int count = 0;
		for (int i = 0; i < preItemset.size(); i++) {
			List<String> tempLine = new ArrayList<String>();
			tempLine.addAll(preItemset.get(i));

			for (int j = i + 1; j < preItemset.size(); j++) {
				if (preItemset.get(i).size() == preItemset.get(j).size()) {

					if (1 == differElemNum(preItemset.get(i), preItemset.get(j))) {
						int index = getDifferIndex(preItemset.get(i), preItemset.get(j));

						tempLine.add(preItemset.get(j).get(index));

						if (isSubSets(tempLine, preItemset)) {

							List<String> aLine = new ArrayList<>();

							for (int m = 0; m < tempLine.size(); m++) {
								aLine.add(tempLine.get(m));
							}

							if (nextItemSetNotHave(aLine, nextItemset))
								nextItemset.add(aLine);
						}
					}
				} // outer if

				if (tempLine.size() > 0)
					tempLine.remove(tempLine.size() - 1);
			} // for j
		}

		return nextItemset;

	}

	private static boolean nextItemSetNotHave(List<String> aLine, List<List<String>> nextItemset) {
		boolean notHave = true;

		for (int i = 0; i < nextItemset.size(); i++) {
			if (aLine.equals(nextItemset.get(i))) {
				notHave = false;
			}
		}

		return notHave;
	}

	private static int getDifferIndex(List<String> list1, List<String> list2) {
		int index = -1;

		for (int i = 0; i < list1.size(); i++) {
			for (int j = 0; j < list1.size(); j++) {
				if (!list1.get(i).equals(list2.get(j))) {
					index = j;
				}
			}

			if (index != -1)
				break;
		}

		return index;
	}

	private static int differElemNum(List<String> list1, List<String> list2) {
		int count = 0;

		boolean flag;

		for (int i = 0; i < list1.size(); i++) {
			flag = true;

			for (int j = 0; j < list1.size(); j++) {
				if (list1.get(i).equals(list2.get(j))) {
					flag = false;
					break;
				}
			}

			if (flag == true) {
				count++;
			}
		}

		return count;
	}

	/**
	 * method following is used to justice whether
	 * 
	 * @param tempList
	 *            all subsets except itself is the subsets of
	 * @param lItemset
	 * 
	 * @return boolean true : all subsets of tempList are all in lItemset\'s set
	 */

	private static boolean isSubSets(List<String> tempList, List<List<String>> lItemset) {

		boolean flag = false;

		for (int i = 0; i < tempList.size(); i++) {
			List<String> testLine = new ArrayList<>();

			for (int j = 0; j < tempList.size(); j++) {
				if (i != j) {
					testLine.add(tempList.get(j));
				}
			}

			for (int k = 0; k < lItemset.size(); k++) {
				if (testLine.equals(lItemset.get(k))) {
					flag = true;
					break;
				}
			}

			if (flag == false) {

				return false;
			}
		}

		return flag; // return true ;
	}

	private static List<List<String>> getLItemset(Map<List<String>, Integer> lItemset) {
		List<List<String>> itemset = new ArrayList<List<String>>();

		Iterator<Map.Entry<List<String>, Integer>> iterator = lItemset.entrySet().iterator();
		Entry<List<String>, Integer> entry;

		while (iterator.hasNext()) {
			entry = iterator.next();
			List<String> key = entry.getKey();

			itemset.add(key);
		}
		return itemset;
	}

	private static void getLKitemset(Map<List<String>, Integer> lkItemset) {
		Iterator<Entry<List<String>, Integer>> iterator = lkItemset.entrySet().iterator();
		Entry<List<String>, Integer> entry;

		while (iterator.hasNext()) {
			entry = iterator.next();

			List<String> key = entry.getKey();
			Integer value = entry.getValue();

			List<String> list = new ArrayList<>();
			for (int i = 0; i < key.size(); i++) {
				list.add(key.get(i));
			}

			result.put(list, value.intValue());
		}

	}

}
